package com.leetcode.根据算法进行分类.动态规划算法相关;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: ZhouBert
 * @date: 2021/3/18
 * @description: 1143. 最长公共子序列
 * https://leetcode-cn.com/problems/longest-common-subsequence/
 */
public class B_1143_最长公共子序列 {

	static B_1143_最长公共子序列 action = new B_1143_最长公共子序列();

	public static void main(String[] args) {
//		test1();
//		test2();
//		test3();
//		test4();
//		test5();
		test6();
	}

	public static void test1() {
		//3
		String text1 = "abcde";
		String text2 = "ace";
		int res = action.longestCommonSubsequence(text1, text2);
		System.out.println("res = " + res);
	}

	public static void test2() {
		//3
		String text1 = "abc";
		String text2 = "abc";
		int res = action.longestCommonSubsequence(text1, text2);
		System.out.println("res = " + res);
	}

	public static void test3() {
		//6
		String text1 = "mhunuzqrkzsnidwbun";
		String text2 = "szulspmhwpazoxijwbq";
		int res = action.longestCommonSubsequence(text1, text2);
		System.out.println("res = " + res);
	}

	public static void test4() {
		//0
		String text1 = "abc";
		String text2 = "def";
		int res = action.longestCommonSubsequence(text1, text2);
		System.out.println("res = " + res);
	}

	public static void test5() {
		//1
		String text1 = "psnw";
		String text2 = "vozsh";
		int res = action.longestCommonSubsequence(text1, text2);
		System.out.println("res = " + res);
		//42 / 44
	}

	/**
	 * 让我的套娃超时的测试用例
	 * 然而当我代码更新的时候，发现超时的用例发生改变了。
	 * 莫非测试用例具有随机性？？？
	 */
	public static void test6() {
		//1
		String text1 = "fcvafurqjylclorwfoladwfqzkbebslwnmpmlkbezkxoncvwhstwzwpqxqtyxozkpgtgtsjobujezgrkvevklmludgtyrmjaxyputqbyxqvupojutsjwlwluzsbmvyxifqtglwvcnkfsfglwjwrmtyxmdgjifyjwrsnenuvsdedsbqdovwzsdghclcdexmtsbexwrszihcpibwpidixmpmxshwzmjgtadmtkxqfkrsdqjcrmxkbkfoncrcvoxuvcdytajgfwrcxivixanuzerebuzklyhezevonqdsrkzetsrgfgxibqpmfuxcrinetyzkvudghgrytsvwzkjulmhanankxqfihenuhmfsfkfepibkjmzybmlkzozmluvybyzsleludsxkpinizoraxonmhwtkfkhudizepyzijafqlepcbihofepmjqtgrsxorunshgpazovuhktatmlcfklafivivefyfubunszyvarcrkpsnglkduzaxqrerkvcnmrurkhkpargvcxefovwtapedaluhclmzynebczodwropwdenqxmrutuhehadyfspcpuxyzodifqdqzgbwhodcjonypyjwbwxepcpujerkrelunstebopkncdazexsbezmhynizsvarafwfmnclerafejgnizcbsrcvcnwrolofyzulcxaxqjqzunedidulspslebifinqrchyvapkzmzwbwjgbyrqhqpolwjijmzyduzerqnadapudmrazmzadstozytonuzarizszubkzkhenaxivytmjqjgvgzwpgxefatetoncjgjsdilmvgtgpgbibexwnexstipkjylalqnupexytkradwxmlmhsnmzuxcdkfkxyfgrmfqtajatgjctenqhkvyrgvapctqtyrufcdobibizihuhsrsterozotytubefutaxcjarknynetipehoduxyjstufwvkvwvwnuletybmrczgtmxctuny";
		String text2 = "nohgdazargvalupetizezqpklktojqtqdivcpsfgjopaxwbkvujilqbclehulatshehmjqhyfkpcfwxovajkvankjkvevgdovazmbgtqfwvejczsnmbchkdibstklkxarwjqbqxwvixavkhylqvghqpifijohudenozotejoxavkfkzcdqnoxydynavwdylwhatslyrwlejwdwrmpevmtwpahatwlaxmjmdgrebmfyngdcbmbgjcvqpcbadujkxaxujudmbejcrevuvcdobolcbstifedcvmngnqhudixgzktcdqngxmruhcxqxypwhahobudelivgvynefkjqdyvalmvudcdivmhghqrelurodwdsvuzmjixgdexonwjczghalsjopixsrwjixuzmjgxydqnipelgrivkzkxgjchibgnqbknstspujwdydszohqjsfuzstyjgnwhsrebmlwzkzijgnmnczmrehspihspyfedabotwvwxwpspypctizyhcxypqzctwlspszonsrmnyvmhsvqtkbyhmhwjmvazaviruzqxmbczaxmtqjexmdudypovkjklynktahupanujylylgrajozobsbwpwtohkfsxeverqxylwdwtojoxydepybavwhgdehafurqtcxqhuhkdwxkdojipolctcvcrsvczcxedglgrejerqdgrsvsxgjodajatsnixutihwpivihadqdotsvyrkxehodybapwlsjexixgponcxifijchejoxgxebmbclczqvkfuzgxsbshqvgfcraxytaxeviryhexmvqjybizivyjanwxmpojgxgbyhcruvqpafwjslkbohqlknkdqjixsfsdurgbsvclmrcrcnulinqvcdqhcvwdaxgvafwravunurqvizqtozuxinytafopmhchmxsxgfanetmdcjalmrolejidylkjktunqhkxchyjmpkvsfgnybsjedmzkrkhwryzan";
		int res = action.longestCommonSubsequence(text1, text2);
		System.out.println("res = " + res);
		//42 / 44
	}




	/**
	 * 感觉这道题神似 {@link C_115_不同的子序列}
	 * 从暴力的角度来分析：
	 * 1.将 text2 拆解并去遍历 text1 ,一个个进行比对，将序列对上后进行统计更新 max；
	 * 2.最终得到 max
	 * 发现：（i1 属于 text1,i2 属于 text2）
	 * if(text1[i1]==text2[i2]) 找到下一个 i12 > i1 && i22 > i2 才能推进；
	 * 而在暴力解法中，要从 i1 找到 i12 的过程就存在重复计算。
	 * 接下来，画一个图：
	 * a	b	c	d	e
	 * a	√
	 * c			√
	 * e					√
	 * 于是问题就转换成为：
	 * 二位数组坐标覆盖的问题，也就是俄罗斯套娃的问题{@link com.leetcode.算法策略相关.动态规划.C_354_俄罗斯套娃信封问题}。
	 * --
	 * 本例程，套娃失败，于是重新以 俄罗斯套娃作为参考，重新写！
	 *
	 * @param text1
	 * @param text2
	 * @return
	 */
	public int longestCommonSubsequenceFail(String text1, String text2) {
		char[] chars1 = text1.toCharArray();
		char[] chars2 = text2.toCharArray();
		int len1 = chars1.length;
		int len2 = chars2.length;
		//boolean[][] dp = new boolean[len1][len2];
		int minLen = Math.min(len1, len2);

		//使用这三个完成统计（这样设计是有缺陷的，因为不能一出现可以套娃的情况就选择套娃！）
		int[][] recorderArr = new int[len1 + len2][2];
		int[] numArr = new int[len1 + len2];
		int max = 0;

		int index = 0;
		//从图上看，即使 任意 dp[i][j] 都是 true
		for (int i = 0; i < len1; i++) {
			for (int j = 0; j < len2; j++) {
				if (chars1[i] == chars2[j]) {
					//去遍历覆盖的位置
					boolean hasPut = false;
					for (int k = 0; k < index; k++) {

						if (i > recorderArr[k][0] && j > recorderArr[k][1]) {
							//进行覆盖
							recorderArr[k] = new int[]{i, j};
							//同时更新统计值
							numArr[k]++;
							//更新最大值
							max = Math.max(max, numArr[k]);

							hasPut = true;
						}
					}
					//如果遍历结束还木有将新的索引放进去，那就重新放一个位置
					if (!hasPut) {
						recorderArr[index] = new int[]{i, j};
						numArr[index]++;

						max = Math.max(max, 1);
						index++;
					}
					if (max == minLen) {
						//当达到两个串中的最小长度时，可以立即退出
						return minLen;
					}
				}
			}
		}
		return max;
	}

	/**
	 * 卧槽泪奔！居然超时了！
	 *
	 * @param text1
	 * @param text2
	 * @return
	 */
	public int longestCommonSubsequence(String text1, String text2) {
		char[] chars1 = text1.toCharArray();
		char[] chars2 = text2.toCharArray();
		int len1 = chars1.length;
		int len2 = chars2.length;
		int minLen = Math.min(len1, len2);

		int size = len1 * len2;
		int[][] tempEnvelopes = new int[size][2];

		int index = 0;
		//从图上看，即使 任意 dp[i][j] 都是 true
		for (int i = 0; i < len1; i++) {
			for (int j = 0; j < len2; j++) {
				if (chars1[i] == chars2[j]) {
					tempEnvelopes[index++] = new int[]{i, j};
				}
			}
		}
		//最终确认的数量
		int[][] envelopes = new int[index][2];
		System.arraycopy(tempEnvelopes, 0, envelopes, 0, index);

		//开始俄罗斯套娃
		//1.进行排序
		Arrays.sort(envelopes, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return o2[1] - o1[1];
				} else {
					return o2[0] - o1[0];
				}
			}
		});
		if (index == 0) {
			return 0;
		}
		//2. DP 处理
		int[] dp = new int[index];
		dp[0] = 1;
		for (int i = 1; i < index; i++) {
			int max = 1;
			for (int j = i - 1; j >= 0; j--) {
				if (envelopes[j][0] > envelopes[i][0] && envelopes[j][1] > envelopes[i][1]) {
					max = Math.max(max, dp[j] + 1);
				}
//				if (j == 0) {
//					break;
//				} else if (envelopes[j][1] <= envelopes[j - 1][1]) {
//					break;
//				}
			}
			if (max == minLen) {
				return minLen;
			}
			dp[i] = max;
		}

		int res = dp[0];
		for (int i = 1; i < index; i++) {
			res = Math.max(res, dp[i]);
		}
		return res;
	}

	/**
	 *
	 * @param text1
	 * @param text2
	 * @return
	 */
	public int longestCommonSubsequenceByDP(String text1, String text2) {
		// 动态规划
		int len1 = text1.length();
		int len2 = text2.length();

		int[][] dp = new int[len1+1][len2+1];

		for (int i=1; i<=len1; ++i) {
			for (int j=1; j<=len2; ++j) {
				if (text1.charAt(i-1) == text2.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		return dp[len1][len2];
	}


}
